#include <cctype>
#include <unordered_map>
class Solution {
public:
    unordered_map<char, int> ht = {
        make_pair('+', 1),
        make_pair('-', 1),
        make_pair('*', 2)
    };
    int solve(string str) {
        if (str[0] == '+' || str[0] == '-') nums.push(0);
        for (int i = 0; i < str.size(); ++i) {
            char x = str[i];
            if (x == '(') {
                opts.push(x);
            } else if (x == ')') {
                while (!opts.empty()) {
                    if (opts.top() != '(') {
                        compute(nums, opts);
                    } else {
                        opts.pop();
                        break;
                    }
                }
            }  else {
                if (isdigit(x)) {
                    string s = to_string(x-'0');
                    while (isdigit(str[i+1])) {
                        s += to_string(str[++i]-'0');
                    }
                    if (!s.empty()) {
                        nums.push(stoi(s));
                    }
                }
                else {
                    while (!opts.empty() && opts.top() != '(') {
                        char prev = opts.top();
                        if (ht[prev] >= ht[x]) {
                            compute(nums, opts);
                        } else {
                            break;
                        }
                    }
                    opts.push(x);
                }
            }
        }
        while (!opts.empty() && opts.top() != '(') {
            compute(nums, opts);
        }
        return nums.top();
    }
    void compute(stack<int>& nums, stack<char>& opts) {
        if (nums.empty() || nums.size() < 2) return;
        if (opts.empty()) return;
        int n2 = nums.top();
        nums.pop();
        int n1 = nums.top();
        nums.pop();
        int res;
        switch (opts.top()) {
            case '*': 
                res = n1 * n2;
                break;
            case '+': 
                res = n1 + n2;
                break;
            case '-': 
                res = n1 - n2;
                break;
        }
        opts.pop();
        nums.push(res);
    }
    stack<int> nums;
    stack<char> opts;
};